package 单周赛.history;

/**
 *
 */
public class 第353场单周赛 {

    public static void main(String[] args) {

        System.out.println(maximumJumps(new int[]{0, 3, 2, 1}, 1));

        System.out.println(maxNonDecreasingLength(new int[]{1, 8}, new int[]{10, 1}));

        System.out.println(checkArray(new int[]{2, 2, 3, 1, 1, 0}, 3));

    }

    /**
     * 动态规划
     * 1，dp[i] 表示从下标 0 开始，到达 nums[i] 的最大跳跃次数
     * 2，fromZero[i] 表示 nums[i] 是否可以从 0 开始跳跃到达
     * 注意：是跳跃次数，不是整数数量
     */
    public static int maximumJumps(int[] nums, int target) {
        int[] dp = new int[nums.length];
        boolean[] fromZero = new boolean[nums.length];
        fromZero[0] = true;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (Math.abs(nums[i] - nums[j]) <= target && fromZero[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    fromZero[i] = fromZero[i] || fromZero[j];
                }
            }
        }
        if (dp[nums.length - 1] == 0) {
            return -1;
        }
        return dp[nums.length - 1];
    }

    /**
     * 动态规划
     * 1，dp[i] 需要保持两个状态，如果取较大值，以 i 结尾的最长非递减子数组的长度是多少
     * 如果取较小值，以 i 结尾的最长非递减子数组的长度是多少
     * 2，dp[i] 的计算只与 dp[i-1] 的状态有关
     */
    public static int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int ans = 1;
        int[] preMax = {Math.max(nums1[0], nums2[0]), 1};
        int[] preMin = {Math.min(nums1[0], nums2[0]), 1};

        for (int i = 1; i < nums1.length; i++) {
            int[] curMax = {Math.max(nums1[i], nums2[i]), 1};
            int[] curMin = {Math.min(nums1[i], nums2[i]), 1};

            if (preMax[0] <= curMax[0]) {
                curMax[1] = Math.max(curMax[1], preMax[1] + 1);
            }
            if (preMin[0] <= curMax[0]) {
                curMax[1] = Math.max(curMax[1], preMin[1] + 1);
            }

            if (preMax[0] <= curMin[0]) {
                curMin[1] = Math.max(curMin[1], preMax[1] + 1);
            }
            if (preMin[0] <= curMin[0]) {
                curMin[1] = Math.max(curMin[1], preMin[1] + 1);
            }

            ans = Math.max(ans, Math.max(curMax[1], curMin[1]));

            preMax = curMax;
            preMin = curMin;
        }
        return ans;
    }

    /**
     * 差分数组
     * nums[i] = sum(diff[0]+...diff[i]) + nums[i]
     */
    public static boolean checkArray(int[] nums, int k) {
        int left = 0, right = k - 1;
        int[] diff = new int[nums.length + 1];
        int diffSum = 0;
        while (left < nums.length) {
            diffSum += diff[left];
            int curNum = diffSum + nums[left];

            if (curNum == 0) {
                left++;
                right++;
                continue;
            }
            if (curNum < 0 || right >= nums.length) {
                return false;
            }
            // diff[left] -= curNum;
            diffSum -= curNum;
            diff[right + 1] += curNum;

            left++;
            right++;
        }
        return true;
    }
}
